package com.zyk.leetcode;

/**
 * @author zhangsan
 * @date 2021/5/29 11:41
 */
public class C1074 {

    // 暴力枚举 枚举子矩阵O(N^4* subR*subC)
    public static int numSubmatrixSumTarget(int[][] matrix, int target) {
        int R = matrix.length, C = matrix[0].length;
        int ans = 0;
        for (int r1 = 0; r1 < R; r1++) {
            for (int c1 = 0; c1 < C; c1++) {

                for (int r2 = r1; r2 < R; r2++) {
                    for (int c2 = c1; c2 < C; c2++) {
                        if(sumSubMatrix(matrix, r1, c1, r2, c2) == target) {
                            ans++;
                        }
                    }
                }

            }
        }
        return ans;
    }

    public static int sumSubMatrix(int[][] matrix, int r1, int c1, int r2, int c2) {
        int sum = 0;
        for (int r = r1; r <= r2; r++) {
            for (int c = c1; c <= c2; c++) {
                sum += matrix[r][c];
            }
        }
        return sum;
    }

    // 前缀和优化
    public static int numSubmatrixSumTarget2(int[][] matrix, int target) {
        int R = matrix.length, C = matrix[0].length;
        int ans = 0;
        int[][] pre = new int[R+1][C+1];
        for (int r = 1; r <= R; r++) {
            for (int c = 1; c <= C; c++) {
                pre[r][c] = matrix[r-1][c-1] + pre[r-1][c] + pre[r][c-1] - pre[r-1][c-1];
            }
        }

        for (int r2 = 1; r2 <= R; r2++) {
            for (int c2 = 1; c2 <= C; c2++) {


                for (int r1 = 1; r1 <= r2; r1++) {
                    for (int c1 = 1; c1 <= c2; c1++) {
                        int sum = pre[r2][c2] - pre[r2][c1-1] - pre[r1-1][c2] + pre[r1-1][c1-1];
                        if(sum == target) ans++;
                    }
                }

            }
        }


        return ans;
    }

    // for test
    public static void main(String[] args) {
        int[][] m = {
                {1,2,3},
                {1,2,3},
                {1,2,3},
        };
        int target = 3;
        System.out.println(numSubmatrixSumTarget2(m, target));
    }

}
